/*
 * Copyright (c) 2012, Markus Weber All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without modification, are
 * permitted provided that the following conditions are met:
 * 
 * Redistributions of source code must retain the above copyright notice, this list of
 * conditions and the following disclaimer. Redistributions in binary form must reproduce the
 * above copyright notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution.
 * 
 * Neither the name of the author nor the names of its contributors may be used to endorse or
 * promote products derived from this software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS
 * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR
 * TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
 * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 * 
 */
package de.dfki.graph.index;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeSet;

import org.apache.log4j.Logger;

import de.dfki.graph.EmptyQueryException;
import de.dfki.graph.LabelType;
import de.dfki.graph.Vertex;


/**
 * Decision tree for efficient retrieval.
 * 
 * @author Markus Weber
 * 
 */
public class DecisionTree implements Serializable {
	/** Generated serial id. */
	private static final long serialVersionUID = -7125158498345802043L;

	/** Logger */
	private transient Logger log = Logger.getLogger(DecisionTree.class);

	/** Decision tree */
	private List<Map<Byte, Node>> tree = new ArrayList<Map<Byte, Node>>();

	/** Sequence for ID generation. */
	private int idSequence = 0;

	/** Counter for the number of sequences. */
	private long numberOfSequences = 0;

	/** Contains all decision. */
	private Set<String> decisions = new HashSet<String>();

	/**
	 * Creates a decision tree.
	 */
	public DecisionTree() {
		super();
	}

	/**
	 * Adds an entry point.
	 * 
	 * @param e
	 * @param fp
	 */
	public void addEntryPoint(Vertex<?> e, String fp) {
		Map<Byte, Node> entry = null;
		if (tree.size() == 0) {
			entry = new Hashtable<Byte, Node>();
			tree.add(entry);
		} else {
			entry = tree.get(0);
		}
		if (entry.containsKey(e.getType().getWeight())) {
			Node n = entry.get(e.getType().getWeight());
			n.labels.add(fp);
		} else {
			entry.put(e.getType().getWeight(), new Node(nodeIDsequence(), e
					.getType().getWeight(), fp));
		}
		decisions.add(fp);
	}

	/**
	 * Adding a sequence.
	 * 
	 * @param treelevel
	 * @param from
	 * @param to
	 * @param sequence
	 * @param decision
	 */
	public void addSequence(int treelevel, Vertex<?> from,
			Vertex<?> to, byte[] sequence, final String decision) {
		Map<Byte, Node> fromLevel = null;
		Map<Byte, Node> toLevel = null;
		if (tree.size() <= treelevel) {
			while (tree.size() <= treelevel) {
				toLevel = new Hashtable<Byte, Node>();
				tree.add(toLevel);
			}
		} else {
			toLevel = tree.get(treelevel);
		}
		fromLevel = tree.get(treelevel - 1);

		Node toNode = null;
		if (fromLevel.containsKey(from.getType().getWeight())) {
			Node fromNode = fromLevel.get(from.getType().getWeight());
			toNode = fromNode.getExactMatch(sequence);
			if (toNode == null) {
				toNode = new Node(nodeIDsequence(), from.getType().getWeight(),
						decision);
			}
			fromNode.addSequence(sequence, toNode, decision);
		} else {
			Node fromNode = new Node(nodeIDsequence(), from.getType().getWeight(),
					decision);
			toNode = new Node(nodeIDsequence(), from.getType().getWeight(),
					decision);
			fromNode.addSequence(sequence, toNode, decision);
			fromLevel.put(from.getType().getWeight(), fromNode);
		}
		numberOfSequences++;
		if (numberOfSequences % 100000000 == 0) {
			log.debug("Sequences added: " + numberOfSequences + " nodes: "
					+ this.idSequence);
		}
		decisions.add(decision);
	}

	/**
	 * Node sequence id.
	 * 
	 * @return
	 */
	public synchronized int nodeIDsequence() {
		return idSequence++;
	}

	/**
	 * Returns the number of nodes.
	 * 
	 * @return
	 */
	public int numberOfNodes() {
		return idSequence;
	}

	/**
	 * Finds matches in the decision tree.
	 * 
	 * @param entities
	 * @return
	 * @throws EmptyQueryException
	 */
	public SortedSet<SearchResult> lookUp(List<byte[]> entities)
			throws EmptyQueryException {
		final int length = entities.size();
		if (entities == null || entities.size() == 0) {
			throw new EmptyQueryException();
		} else if(tree.isEmpty()) {
			return new TreeSet<SearchResult>();
		}
		
		SearchResult res = new SearchResult();
		Map<Byte, Node> entry = tree.get(0);

		Node entryNode = findClosestEntryPoint(entities.get(0)[0], entry);
		entities.remove(0);
		SortedSet<SearchResult> result = treeTraversal(entryNode, entities, 0,
				res, length);
		return result;
	}

	/**
	 * Traversal of the tree.
	 * 
	 * @param entryNode
	 * @param entities
	 * @param length
	 */
	private SortedSet<SearchResult> treeTraversal(Node entryNode,
			List<byte[]> entities, int pos, SearchResult res, int length) {
		// termination criterion
		if (entryNode == null) { // inexact matches
			SortedSet<SearchResult> results = new TreeSet<SearchResult>();
			if (res.getResult() != null) {
				results.add(res);
			}
			return results;
		}
		if (entities.size() <= pos) {
			SortedSet<SearchResult> results = new TreeSet<SearchResult>();
			for (String s : entryNode.labels) {
				SearchResult r = res.cloneResult(s);
				results.add(r);
			}
			return results;
		}
		SortedSet<SearchResult> result = new TreeSet<SearchResult>();
		Node current = entryNode;
		Set<Node> best = current.bestMatch(entities.get(pos));
		pos++;
		if(best.size() == 0) {
			// maximum common subgraph
			for(String label : entryNode.labels) {
				result.add(new SearchResult((float)(pos + 1) / (entities.size() + 1) ,label));
			}
		}
		for (Node n : best) {
			result.addAll(treeTraversal(n, entities, pos, res.cloneResult(),
					length));
		}
		return result;

	}

	/**
	 * Looks for the exact match, if there is no match the methods chooses the
	 * closest match.
	 * 
	 * @param entities
	 * @param entry
	 */
	private Node findClosestEntryPoint(byte entityType, Map<Byte, Node> entry) {
		Node n = entry.get(entityType);
		if (n != null) {
			return n;
		}
		double bestMatch = 0.0;
		for (Byte key : entry.keySet()) {
			double similarity = compareEntities(key, entityType);
			if (similarity > bestMatch) {
				n = entry.get(entityType);
			}
		}
		return n;
	}

	/**
	 * Finds the type with by the uid.
	 * 
	 * @param uid
	 * @return
	 */
	protected LabelType findType(byte uid) {

		
		return null;
	}

	/**
	 * Compares entities for similarity measure
	 * 
	 * @param nodeUID
	 * @param queryUID
	 * @return
	 */
	private double compareEntities(byte nodeUID, byte queryUID) {
		LabelType node = findType(nodeUID);
		LabelType query = findType(queryUID);
		if (node.getWeight() == query.getWeight()) {
			return 1.0;
		} else {
			return .0;
		}
	}

	/**
	 * Checks if the decision is already considered in the decision tree.
	 * 
	 * @param decision
	 * @return
	 */
	public boolean containsDecision(final String decision) {
		return this.decisions.contains(decision);
	}

	/**
	 * Clears the tree.
	 */
	public synchronized void clear() {
		this.tree.clear();
		this.decisions.clear();
		System.gc();
	}
}
